#!/usr/bin/env python
# -*- coding: utf-8 -*-
'''
autor: Jose Jasnau Caeiro
data: 7 de maio de 2012

arvores de pesquisa binária
'''

class No:
    def __init__(self, key, valor):
        self.key = key
        self.valor = valor

        self.parent = None
        self.left   = None
        self.right  = None
        pass

    def __str__(self):
        s = str(self.key) + ' : ' + str(self.valor)
        s += '('
        if self.parent == None:
            s += 'None'  + ', ' 
        else:
            s += str(self.parent.key) + ', ' 

        if self.left == None:
            s += 'None'  + ', ' 
        else:
            s += str(self.left.key) + ', ' 

        if self.right == None:
            s += 'None' + ')' 
        else:
            s += str(self.right.key) + ')' 
        return s

class ArvorePesquisaBinaria:
    def __init__(self):
        self.root = None

    def insert(self, z):
        y = None
        x = self.root
        while x != None:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def search(self, x, k):
        if x == None or k == x.key:
            return x
        if k < x.key:
            return self.search(x.left, k)
        else:
            return self.search(x.right, k)

    def minimum(self, x):
        while x.left != None:
            x = x.left
        return x

    def maximum(self, x):
        while x.right != None:
            x = x.right
        return x

    def sucessor(self, x):
        if x.right != None:
            return minimum(x.right)
        y = x.parent
        while y != None and x == y.right:
            x = y
            y = y.parent
        return y

    def transplant(self, u, v):
        if u.parent == None:
            self.root = v
        elif u == u.parent.left:
            u.parent.left = v
        else:
            u.parent.right = v
        if v != None:
            v.parent = u.parent

    def delete(self, z):
        if z.left == None:
            self.transplant(z, z.right)
        elif z.right == None:
            self.transplant(z, z.left)
        else:
            y = self.minimum(z.right)
            if y.parent != z:
                self.transplant(y, y.right)
                y.right = z.right
                y.right.parent = y
            self.transplant(z, y)
            y.left = z.left
            y.left.parent = y

    def inorder_walk(self, x, lista):
        if x != None:
            self.inorder_walk(x.left, lista)
            lista.append( x )
            self.inorder_walk(x.right, lista)
            
    pass


nos = [None for k in range(9)]

nos[0] = No(12, "Renoir")
nos[1] = No(5, "van Gogh")
nos[2] = No(18, "Picasso")
nos[3] = No(2, "Manet")
nos[4] = No(9, "da Vinci")
nos[5] = No(15, "Miguel Angelo")
nos[6] = No(19, "Rafael")
nos[7] = No(17, "Goya")
nos[8] = No(13, "Turner")

arv = ArvorePesquisaBinaria()

arv.insert(nos[0])
arv.insert(nos[1])
arv.insert(nos[2])
arv.insert(nos[3])
arv.insert(nos[4])
arv.insert(nos[5])
arv.insert(nos[6])
arv.insert(nos[7])
arv.insert(nos[8])

print "INORDER"
lista = []
arv.inorder_walk(arv.root, lista)
for x in lista:
    print x

print
for x in nos:
    print x

print "PESQUISA"
print arv.search(arv.root, 15)

print "MINIMO"
print arv.minimum(arv.root)

print "MAXIMO"
print arv.maximum(arv.root)

print "SUCESSOR"
print arv.sucessor(nos[4])

print "DELETE"
print arv.delete(nos[2])

for x in nos:
    print x

print "PESQUISA"
print arv.search(arv.root, 18)

print
print "INORDER"
lista = []
arv.inorder_walk(arv.root, lista)
for x in lista:
    print x
